home *** CD-ROM | disk | FTP | other *** search
/ QRZ! Ham Radio 6 / QRZ Ham Radio Callsign Database - Volume 6.iso / mac / files / amiga / csrc720j.lzh / lzhuf.c < prev    next >
C/C++ Source or Header  |  1993-04-22  |  13KB  |  576 lines
  1. /**************************************************************
  2.    lzhuf.c
  3.    written by Haruyasu Yoshizaki 11/20/1988
  4.    some minor changes 4/6/1989
  5.    comments translated by Haruhiko Okumura 4/7/1989
  6. Taken from the FBB distribution and modified to do an in-memory
  7. (de)compression.
  8. **************************************************************/
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <string.h>
  12. #include <ctype.h>
  13.  
  14. unsigned long int  textsize = 0, codesize = 0;
  15. FILE  *infl;
  16. extern short huf_error;
  17. extern unsigned char gethuf();
  18. extern char tmpstr[];
  19. char wterr[] = "Can't write.";
  20.  
  21.  
  22. /********** LZSS compression **********/
  23. /* Confirmed by F6FBB that N should be 2048 */
  24. #define N            2048   /*4096*/    /* buffer size */
  25. #define F               60      /* lookahead buffer size */
  26. #define THRESHOLD       2
  27. #define NIL             N       /* leaf of tree */
  28. #ifndef MCH_AMIGA
  29. unsigned char
  30.       text_buf[N + F - 1];
  31. int             match_position, match_length,
  32.       *lson, rson[N + 257], dad[N + 1];
  33. #else
  34. extern short block_cancel;
  35. unsigned char *text_buf;
  36. int    match_position, match_length,
  37.       *lson, *rson, *dad;
  38. #endif
  39. void InitTree(void)  /* initialize trees */
  40. {
  41.    int  i;
  42.  
  43.    for (i = N + 1; i <= N + 256; i++)
  44.       rson[i] = NIL;                  /* root */
  45.    for (i = 0; i < N; i++)
  46.       dad[i] = NIL;                   /* node */
  47. }
  48.  
  49. void InsertNode(int r)  /* insert to tree */
  50. {
  51.    int  i, p, cmp;
  52.    unsigned char  *key;
  53.    unsigned c;
  54.  
  55.    cmp = 1;
  56.    key = &text_buf[r];
  57.    p = N + 1 + key[0];
  58.    rson[r] = lson[r] = NIL;
  59.    match_length = 0;
  60.    for ( ; ; ) {
  61.       if (cmp >= 0) {
  62.          if (rson[p] != NIL)
  63.             p = rson[p];
  64.          else {
  65.             rson[p] = r;
  66.             dad[r] = p;
  67.             return;
  68.          }
  69.       } else {
  70.          if (lson[p] != NIL)
  71.             p = lson[p];
  72.          else {
  73.             lson[p] = r;
  74.             dad[r] = p;
  75.             return;
  76.          }
  77.       }
  78.       for (i = 1; i < F; i++)
  79.          if ((cmp = key[i] - text_buf[p + i]) != 0)
  80.             break;
  81.       if (i > THRESHOLD) {
  82.          if (i > match_length) {
  83.             match_position = ((r - p) & (N - 1)) - 1;
  84.             if ((match_length = i) >= F)
  85.                break;
  86.          }
  87.          if (i == match_length) {
  88.             if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
  89.                match_position = c;
  90.             }
  91.          }
  92.       }
  93.    }
  94.    dad[r] = dad[p];
  95.    lson[r] = lson[p];
  96.    rson[r] = rson[p];
  97.    dad[lson[p]] = r;
  98.    dad[rson[p]] = r;
  99.    if (rson[dad[p]] == p)
  100.       rson[dad[p]] = r;
  101.    else
  102.       lson[dad[p]] = r;
  103.    dad[p] = NIL;  /* remove p */
  104. }
  105.  
  106. void DeleteNode(int p)  /* remove from tree */
  107. {
  108.    int  q;
  109.  
  110.    if (dad[p] == NIL)
  111.       return;                 /* not registered */
  112.    if (rson[p] == NIL)
  113.       q = lson[p];
  114.    else
  115.    if (lson[p] == NIL)
  116.       q = rson[p];
  117.    else {
  118.       q = lson[p];
  119.       if (rson[q] != NIL) {
  120.          do {
  121.             q = rson[q];
  122.          } while (rson[q] != NIL);
  123.          rson[dad[q]] = lson[q];
  124.          dad[lson[q]] = dad[q];
  125.          lson[q] = lson[p];
  126.          dad[lson[p]] = q;
  127.       }
  128.       rson[q] = rson[p];
  129.       dad[rson[p]] = q;
  130.    }
  131.    dad[q] = dad[p];
  132.    if (rson[dad[p]] == p)
  133.       rson[dad[p]] = q;
  134.    else
  135.       lson[dad[p]] = q;
  136.    dad[p] = NIL;
  137. }
  138.  
  139. /* Huffman coding */
  140.  
  141. #define N_CHAR          (256 - THRESHOLD + F)
  142.             /* kinds of characters (character code = 0..N_CHAR-1) */
  143. #define T               (N_CHAR * 2 - 1)        /* size of table */
  144. #define R               (T - 1)                 /* position of root */
  145. #define MAX_FREQ        0x8000    /* updates tree when the */
  146.                                   /* root frequency comes to this value. */
  147. typedef unsigned char uchar;
  148.  
  149.  
  150. /* table for encoding and decoding the upper 6 bits of position */
  151. /* I've moved these tables into another file so I don't have to print them
  152.    out all the time
  153. */
  154. /* for encoding */
  155. extern uchar p_len[];
  156.  
  157. extern uchar p_code[];
  158.  
  159. /* for decoding */
  160. extern uchar d_code[];
  161.  
  162. extern uchar d_len[];
  163.  
  164. unsigned freq[T + 1];   /* frequency table */
  165.  
  166. int prnt[T + N_CHAR];   /* pointers to parent nodes, except for the */
  167.          /* elements [T..T + N_CHAR - 1] which are used to get */
  168.          /* the positions of leaves corresponding to the codes. */
  169.  
  170. int son[T];             /* pointers to child nodes (son[], son[] + 1) */
  171.  
  172. unsigned getbuf = 0;
  173. uchar getlen = 0;
  174.  
  175. int GetBit(void)        /* get one bit */
  176. {
  177.    int i;
  178.  
  179.    while (getlen <= 8) {
  180.       i = gethuf();
  181.       getbuf |= i << (8 - getlen);
  182.       getlen += 8;
  183.    }
  184.    i = getbuf;
  185.    getbuf <<= 1;
  186.    getlen--;
  187.    return (i < 0);
  188. }
  189.  
  190. int GetByte(void)       /* get one byte */
  191. {
  192.    unsigned i;
  193.  
  194.    while (getlen <= 8) {
  195.       i = gethuf();
  196.       getbuf |= i << (8 - getlen);
  197.       getlen += 8;
  198.    }
  199.    i = getbuf;
  200.    getbuf <<= 8;
  201.    getlen -= 8;
  202.    return i >> 8;
  203. }
  204.  
  205. unsigned putbuf = 0;
  206. uchar putlen = 0;
  207.  
  208. void Putcode(int l, unsigned c)         /* output c bits of code */
  209. {
  210.    putbuf |= c >> putlen;
  211.    if ((putlen += l) >= 8) {
  212.       puthuf(putbuf >> 8);
  213.       if ((putlen -= 8) >= 8) {
  214.          puthuf(putbuf);
  215.          codesize += 2;
  216.          putlen -= 8;
  217.          putbuf = c << (l - putlen);
  218.       } else {
  219.          putbuf <<= 8;
  220.          codesize++;
  221.       }
  222.    }
  223. }
  224.  
  225.  
  226. /* initialization of tree */
  227.  
  228. void StartHuff(void)
  229. {
  230.    int i, j;
  231.  
  232.    for (i = 0; i < N_CHAR; i++) {
  233.       freq[i] = 1;
  234.       son[i] = i + T;
  235.       prnt[i + T] = i;
  236.    }
  237.    i = 0; j = N_CHAR;
  238.    while (j <= R) {
  239.       freq[j] = freq[i] + freq[i + 1];
  240.       son[j] = i;
  241.       prnt[i] = prnt[i + 1] = j;
  242.       i += 2; j++;
  243.    }
  244.    freq[T] = 0xffff;
  245.    prnt[R] = 0;
  246. }
  247.  
  248.  
  249. /* reconstruction of tree */
  250.  
  251. void reconst(void)
  252. {
  253.    int i, j, k;
  254.    unsigned f, l;
  255.  
  256.    /* collect leaf nodes in the first half of the table */
  257.    /* and replace the freq by (freq + 1) / 2. */
  258.    j = 0;
  259.    for (i = 0; i < T; i++) {
  260.       if (son[i] >= T) {
  261.          freq[j] = (freq[i] + 1) / 2;
  262.          son[j] = son[i];
  263.          j++;
  264.       }
  265.    }
  266.    /* begin constructing tree by connecting sons */
  267.    for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
  268.       k = i + 1;
  269.       f = freq[j] = freq[i] + freq[k];
  270.       for (k = j - 1; f < freq[k]; k--);
  271.       k++;
  272.       l = (j - k) * 2;
  273.       memmove(&freq[k + 1], &freq[k], l);
  274.       freq[k] = f;
  275.       memmove(&son[k + 1], &son[k], l);
  276.       son[k] = i;
  277.    }
  278.    /* connect prnt */
  279.    for (i = 0; i < T; i++) {
  280.       if ((k = son[i]) >= T) {
  281.          prnt[k] = i;
  282.       } else {
  283.          prnt[k] = prnt[k + 1] = i;
  284.       }
  285.    }
  286. }
  287.  
  288.  
  289. /* increment frequency of given code by one, and update tree */
  290.  
  291. void update(int c)
  292. {
  293.    int i, j, k, l;
  294.  
  295.    if (freq[R] == MAX_FREQ) {
  296.       reconst();
  297.    }
  298.    c = prnt[c + T];
  299.    do {
  300.       k = ++freq[c];
  301.  
  302.       /* if the order is disturbed, exchange nodes */
  303.       if (k > freq[l = c + 1]) {
  304.          while (k > freq[++l]);
  305.          l--;
  306.          freq[c] = freq[l];
  307.          freq[l] = k;
  308.  
  309.          i = son[c];
  310.          prnt[i] = l;
  311.          if (i < T) prnt[i + 1] = l;
  312.  
  313.          j = son[l];
  314.          son[l] = i;
  315.  
  316.          prnt[j] = c;
  317.          if (j < T) prnt[j + 1] = c;
  318.          son[c] = j;
  319.  
  320.          c = l;
  321.       }
  322.    } while ((c = prnt[c]) != 0);   /* repeat up to root */
  323. }
  324.  
  325. unsigned code, len;
  326.  
  327. EncodeChar(unsigned c)
  328. {
  329.    unsigned i;
  330.    int j, k;
  331.  
  332.    i = 0;
  333.    j = 0;
  334.    k = prnt[c + T];
  335.  
  336.    /* travel from leaf to root */
  337.    do {
  338.       i >>= 1;
  339.  
  340.       /* if node's address is odd-numbered, choose bigger brother node */
  341.       if (k & 1) i += 0x8000;
  342.  
  343.       j++;
  344.    } while ((k = prnt[k]) != R);
  345.    Putcode(j, i);
  346.    code = i;
  347.    len = j;
  348.    update(c);
  349. }
  350.  
  351. void EncodePosition(unsigned c)
  352. {
  353.    unsigned i;
  354.  
  355.    /* output upper 6 bits by table lookup */
  356.    i = c >> 6;
  357.    Putcode(p_len[i], (unsigned)p_code[i] << 8);
  358.  
  359.    /* output lower 6 bits verbatim */
  360.    Putcode(6, (c & 0x3f) << 10);
  361. }
  362.  
  363. void EncodeEnd(void)
  364. {
  365.    if (putlen) {
  366.       puthuf(putbuf >> 8);
  367.       codesize++;
  368.    }
  369. }
  370.  
  371. int DecodeChar(void)
  372. {
  373.    unsigned c;
  374.  
  375.    c = son[R];
  376.  
  377.    /* travel from root to leaf, */
  378.    /* choosing the smaller child node (son[]) if the read bit is 0, */
  379.    /* the bigger (son[]+1} if 1 */
  380.    while (c < T) {
  381.       c += GetBit();
  382.       c = son[c];
  383.    }
  384.    c -= T;
  385.    update(c);
  386.    return c;
  387. }
  388.  
  389. int DecodePosition(void)
  390. {
  391.    unsigned i, j, c;
  392.  
  393.    /* recover upper 6 bits from table */
  394.    i = GetByte();
  395.    c = (unsigned)d_code[i] << 6;
  396.    j = d_len[i];
  397.  
  398.    /* read lower 6 bits verbatim */
  399.    j -= 2;
  400.    while (j--) {
  401.       i = (i << 1) + GetBit();
  402.    }
  403.    return c | (i & 0x3f);
  404. }
  405.  
  406. /* compression */
  407.  
  408. Encode(void)  /* compression */
  409. {
  410.    int  i, c, len, r, s, last_match_length;
  411. /* Unfortunately, I don't know the true size of the file until I read the
  412.    whole thing because I have to map LF into CR/LF. So the message is
  413.    first written into the file t:fbb.tmp and then the file descriptor
  414.    infl is left open for Encode to deal with the file.
  415.    The calling routine has already written out the SOH header and
  416.    initialized the puthuf routine.
  417. */
  418.    putbuf = 0;
  419.    putlen = 0;
  420.    codesize = 0;
  421.    fseek(infl, 0L, SEEK_END);
  422.    textsize = ftell(infl);
  423.    /* Have to write the long out in IBM order ... low byte first */
  424.    puthuf((unsigned char)(textsize&0xff));
  425.    puthuf((unsigned char)((textsize >> 8) & 0xff));
  426.    puthuf((unsigned char)((textsize >> 16) & 0xff));
  427.    puthuf((unsigned char)((textsize >> 24) & 0xff));
  428.    rewind(infl);
  429.    textsize = 0;                   /* rewind and re-read */
  430.  
  431.    StartHuff();
  432.    InitTree();
  433.    s = 0;
  434.    r = N - F;
  435.    for (i = s; i < r; i++)
  436.       text_buf[i] = ' ';
  437.    for (len = 0; len < F && (c = getc(infl)) != EOF; len++) {
  438.       text_buf[r + len] = c;
  439.    }
  440.    textsize = len;
  441.    for (i = 1; i <= F; i++)
  442.       InsertNode(r - i);
  443.    InsertNode(r);
  444.    do {
  445.       if (match_length > len)
  446.          match_length = len;
  447.       if (match_length <= THRESHOLD) {
  448.          match_length = 1;
  449.          EncodeChar(text_buf[r]);
  450.       } else {
  451.          EncodeChar(255 - THRESHOLD + match_length);
  452.          EncodePosition(match_position);
  453.       }
  454.       last_match_length = match_length;
  455.       for (i = 0; i < last_match_length &&
  456.             (c = getc(infl)) != EOF; i++) {
  457.          DeleteNode(s);
  458.          text_buf[s] = c;
  459.          if (s < F - 1)
  460.             text_buf[s + N] = c;
  461.          s = (s + 1) & (N - 1);
  462.          r = (r + 1) & (N - 1);
  463.          InsertNode(r);
  464.       }
  465.       while (i++ < last_match_length) {
  466.          DeleteNode(s);
  467.          s = (s + 1) & (N - 1);
  468.          r = (r + 1) & (N - 1);
  469.          if (--len) InsertNode(r);
  470.       }
  471. #ifndef MCH_AMIGA
  472.    } while (len > 0);
  473. #else
  474.    } while ((len > 0) && !block_cancel);
  475.    if(block_cancel)return(1);
  476. #endif
  477.  
  478.    EncodeEnd();
  479.    closehuf();
  480.    return(block_cancel);
  481. }
  482.  
  483. Decode(void)  /* recover */
  484. {
  485.    register int  i, j, k;
  486.    int r, c;
  487.    register unsigned long lzcount;
  488.    getbuf = 0;
  489.    getlen = 0;
  490.    codesize = 0;
  491.    /* get textsize from the first block of data
  492.    */
  493.    textsize = (gethuf() & 0xff);
  494.    textsize |= ((gethuf() & 0xff) << 8) & 0xff00;
  495.    textsize |= ((gethuf() & 0xff) << 16) & 0xff0000L;
  496.    textsize |= ((gethuf() & 0xff) << 24) & 0xff000000L;
  497.    StartHuff();
  498.    for (i = 0; i < N - F; i++)
  499.       text_buf[i] = ' ';
  500.    r = N - F;
  501. #ifndef MCH_AMIGA
  502.    for (lzcount = 0; lzcount < textsize; ) {
  503. #else
  504.    for (lzcount = 0;(lzcount < textsize) && !block_cancel; ) {
  505. #endif
  506.       c = DecodeChar();
  507.       if(huf_error)break;
  508.       if (c < 256) {
  509.          putdec(c);
  510.          text_buf[r++] = c;
  511.          r &= (N - 1);
  512.          lzcount++;
  513.       } else {
  514.          i = (r - DecodePosition() - 1) & (N - 1);
  515.          if(huf_error)break;
  516.          j = c - 255 + THRESHOLD;
  517.          for (k = 0; k < j; k++) {
  518.             c = text_buf[(i + k) & (N - 1)];
  519.             putdec(c);
  520.             if(block_cancel)break;
  521.             text_buf[r++] = c;
  522.             r &= (N - 1);
  523.             lzcount++;
  524.          }
  525.       }
  526.    }
  527.    if(huf_error || block_cancel)return(1);
  528.    closedec();
  529.    return(block_cancel);
  530. }
  531. extern char *out_buf_adr,*yapp_buf;
  532.  
  533. fbb_alloc()
  534. {
  535.    if((out_buf_adr = AllocMem(260,MEMF_PUBLIC|MEMF_CHIP)) == NULL) {
  536.       fbb_free();
  537.       return(1);
  538.    }
  539.    if((yapp_buf = AllocMem(260,MEMF_PUBLIC|MEMF_CHIP)) == NULL) {
  540.       fbb_free();
  541.       return(1);
  542.    }
  543.    if((text_buf = AllocMem(N+F-1,MEMF_PUBLIC|MEMF_CHIP)) == NULL) {
  544.       fbb_free();
  545.       return(1);
  546.    }
  547.    if((lson = AllocMem((N+1)*sizeof(int),MEMF_PUBLIC|MEMF_CHIP)) == NULL) {
  548.       fbb_free();
  549.       return(1);
  550.    }
  551.    if((rson = AllocMem((N+257)*sizeof(int),MEMF_PUBLIC|MEMF_CHIP)) == NULL) {
  552.       fbb_free();
  553.       return(1);
  554.    }
  555.    if((dad = AllocMem((N+1)*sizeof(int),MEMF_PUBLIC|MEMF_CHIP)) == NULL) {
  556.       fbb_free();
  557.       return(1);
  558.    }
  559.    return(0);
  560. }
  561. fbb_free()
  562. {
  563.    if(out_buf_adr)FreeMem(out_buf_adr,260);
  564.    out_buf_adr = 0;
  565.    if(yapp_buf)FreeMem(yapp_buf,260);
  566.    yapp_buf = 0;
  567.    if(text_buf)FreeMem(text_buf,N+F-1);
  568.    text_buf = 0;
  569.    if(lson)FreeMem(lson,(N+1)*sizeof(int));
  570.    lson = 0;
  571.    if(rson)FreeMem(rson,(N+257)*sizeof(int));
  572.    rson = 0;
  573.    if(dad)FreeMem(dad,(N+1)*sizeof(int));
  574.    dad = 0;
  575. }
  576.